package com.ntd.study.data.structure;

import java.util.*;

/**
 * 数据结构相关内容
 */
public class DataStructure {
    /**
     * 数组
     * 1.采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)
     * 2.通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)
     * 3.对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式
     * 4.一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
     *
     * 线性链表
     * 1.链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)
     * 2.而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
     *
     * 二叉树
     * 1.对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)
     *
     * 哈希表
     * 1.增，删，查时间复杂度为O(1) - 不考录hash冲突的情况下
     * 2.hash表的主干就是数组
     * 3.存储位置=hash(内容) - hash函数是哈希表优略的关键，与传统数组的区别最重要的也就是hash函数
     * 4.hash冲突的解决方案 - 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法
     * 5.HashMap即是采用了链地址法，也就是数组+链表的方式 - 当数组地址冲突则在同一个数组位置采用链表形式
     *
     * 1. 线性表 - 常以栈、队列、字符串等特殊形式使用
     * |-- 顺序表
     * |---- 队列(Queue) - 简称队，是一种运算受限的线性表，只允许一端插入，一端删除，先进后出 - 删除队首元素必须将数组其他元素向前移动一个位置，执行出队就需要O(n)
     * |-- 链式表
     * 2. 非线性表 - 数据见的关系是一对多、多对一等
     * |-- 图
     * |-- 树
     * |---- 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为书的节点，所定义的关系称为父子关系，父子关系在树的节点之间建立了一个层次机构，这种层次结构中有一个节点具有特殊的地位，这个节点称为树的根节点，或简称为树根。
     * |---- 二叉树 - 每个节点的度均不超过2的有序树，称为二叉树 - 二叉树中每个节点的子节点只能是 0/1/2 个，并且每个子节点都有左右之分。
     * |------ 满二叉树 - 不完全二叉树
     *
     *
     *
     *
     */
    /**
     * 枚举
     */
    Enum anEnum;
    /**
     * 位集合
     */
    BitSet bitSet;
    /**
     * 向量
     */
    Vector vector;
    /**
     * 栈
     */
    Stack stack;
    /**
     * 字典类型
     */
    Dictionary dictionary;
    /**
     * 属性
     * 继承 HashTable
     */
    Properties properties;
}
